/**
 * 
 */
package net.sf.graph4j.element.graph;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import net.sf.graph4j.element.AbstractPropertied;

/**
 * @author chen cong
 * 
 */
public class Graph extends AbstractPropertied {

	List<Vertex> vertices = new ArrayList<Vertex>();

	List<Edge> edges = new ArrayList<Edge>();

	Directed directed = Directed.False;
	
	Weighted weighted = Weighted.False;

	/**
	 * 
	 */
	public Graph() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param directed
	 */
	public Graph(Directed directed) {
		// TODO Auto-generated constructor stub
		this.directed = directed;
	}

	/**
	 * @param directed
	 * @param weighted
	 */
	public Graph(Directed directed, Weighted weighted) {
		super();
		// TODO Auto-generated constructor stub
		this.directed = directed;
		this.weighted = weighted;
	}

	/**
	 * @return Returns the edges.
	 */
	public List<Edge> getEdges() {
		return edges;
	}

	/**
	 * @return Returns the vertices.
	 */
	public List<Vertex> getVertices() {
		return vertices;
	}

	public Directed getDirected() {
		return directed;
	}

	public void setDirected(Directed directed) {
		this.directed = directed;
	}

	/**
	 * @return Returns the weighted.
	 */
	public Weighted getWeighted() {
		return weighted;
	}

	/**
	 * @param weighted The weighted to set.
	 */
	public void setWeighted(Weighted weighted) {
		this.weighted = weighted;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.util.Set#add(E)
	 */
	public boolean addEdge(Edge e) {
		return edges.add(e);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.util.Set#add(E)
	 */
	public boolean addVertex(Vertex arg0) {
		return vertices.add(arg0);
	}

	@Deprecated
	public void addEdge(Vertex source, Vertex target) {
		Edge edge = new Edge(source, target);
		edges.add(edge);
	}

	@Deprecated
	public Vertex newVertex(String name) {
		Vertex v = new Vertex();
		v.getProperties().put(PropertyName, name);
		vertices.add(v);
		return v;
	}

	@Deprecated
	public Edge newDirectedEdge(String sourceName, String targetName) {
		Vertex u = getVertexByName(sourceName);
		Vertex v = getVertexByName(targetName);
		return newDirectedEdge(u, v);
	}

	@Deprecated
	public Edge newDirectedEdge(Vertex source, Vertex target) {
		Edge e = new Edge(Directed.False, source, target);
		edges.add(e);
		return e;
	}

	public Vertex getVertexByName(String name) {
		for (Vertex v : vertices) {
			if (name != null
					&& name.equals(v.getProperties().get(PropertyName)))
				return v;
		}
		return null;
	}
	
	public Edge getEdgeByVertex (Vertex source, Vertex target) {
		for (Edge e : edges) {
			if (e.source == source && e.target == target)
				return e;
			if (directed == Directed.False && e.target == source && e.source == target)
				return e;
		}
		return null;
	}
	
	public Edge getReverseEdge (Edge edge) {
		assert (directed == Directed.True);
		return getEdgeByVertex (edge.target, edge.source);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return super.toString() + "(" + vertices.size() + " vertices, "
				+ edges.size() + " edges)";
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.util.Set#contains(java.lang.Object)
	 */
	public boolean contains(Vertex v) {
		return vertices.contains(v);
	}

	public boolean contains(Edge e) {
		return vertices.contains(e.getSource())
				&& vertices.contains(e.getTarget());
	}
	
	public boolean containsEdge (Vertex source, Vertex target) {
		return getEdgeByVertex (source, target) != null;
	}
	
	public double[][] weightMatrix () {
		
		double[][] data = new double[vertices.size()][vertices.size()];
		for (int i=0; i<data.length; i++)
			Arrays.fill(data[i], Double.POSITIVE_INFINITY);
		
		for (int i=0; i<data.length; i++)
			data[i][i] = 0;
		
		for (Edge e : edges) {
			
			if (data [vertices.indexOf(e.getSource())][vertices.indexOf(e.getTarget())] > e.weight) {
			
				data [vertices.indexOf(e.getSource())][vertices.indexOf(e.getTarget())] = e.weight;
				
				if (directed == Directed.False) {
					data [vertices.indexOf(e.getTarget())][vertices.indexOf(e.getSource())] = e.weight;
				}
			}
		}
		
		return data;
	}

	/* (non-Javadoc)
	 * @see net.sf.graph4j.element.AbstractPropertied#clone()
	 */
	@Override
	public Graph clone() throws CloneNotSupportedException {
		// TODO Auto-generated method stub
		GraphFactory factory = new GraphFactory();
		Graph g = factory.produceGraph();
		
		Map<Vertex, Vertex> old2New = new HashMap<Vertex, Vertex>();
		
		g.setDirected(this.directed);
		g.setWeighted(this.weighted);
		
		for (Vertex v : vertices) {
			Vertex newV = v.clone();
			g.addVertex(newV);
			old2New.put(v, newV);
		}
		
		for (Edge e : edges) {
			Edge newE = factory.produceEdge(g, old2New.get(e.getSource()), old2New.get(e.getTarget()));
			newE.weight = e.weight;
			newE.putAllProperty(e.getProperties());
		}
		return g;
	}
}
